#This is a file that generate a random instance of knapsack problem

import cplex
import random
# Thinking of design the covers and cover classes
# covers(A, b)
# covers.set_inequalities(prob)
# covers.update_inequalities(prob)
# construct the min_covers from A and b

# cover.ind
# cover.val
# cover.max_val
# cover.isminimal()
# cover.islifted()

#from itertools import *
#def genkpineql(n, a, b):
def powerset(lst):
    ind = range(len(lst))
    P = reduce(lambda result, x: result + [subset + [x] for subset in result], lst, [[]])
    I = reduce(lambda result, x: result + [subset + [x] for subset in result], ind, [[]])
    return zip(I, P)

def cumsum(seq):
    cum_sum = []
    y = 0
    for i in seq:   # <--- i will contain elements (not indices) from n
        y += i    # <--- so you need to add i, not n[i]
        cum_sum.append(y)
    return cum_sum

def test_cover(coefs, b):
    return sum(coefs) > b

# this function extend the cover
def extend_cover(cover, A):
    n = len(A)
    
    # how to keep track of the max_cover_val?
    coefs = [A[i] for i in cover]
    max_cover_val = max(coefs)

    extra_items = []

    for i in range(n):
        if i not in cover and A[i] >= max_cover_val:
            extra_items.append(i)

    ext_cover = cover + extra_items

    return ext_cover

def test_cover_minimal(coefs, b):
    # test cover condition
    if sum(coefs) <= b:
        return False

    # test minimality
    for a in coefs:
        if sum(coefs) - a > b:
            return False
            break

    return True


def genkp(n, a, b):
    #seed = 100
    #random.seed(seed)
    prob = cplex.Cplex()
    prob.objective.set_sense(prob.objective.sense.maximize)
    
    #Add Variables
    varnames = ["x" + str(i) for i in range(n)]
    varcosts = [random.randint(3, 5) for i in range(n)]
    vartypes = ["B"]*n
    prob.variables.add(obj = varcosts,
                       types = vartypes,
                       names = varnames)


    #Populate knapsack constraints
    kpnames = ["k"]
    kcoefs = [random.randint(1, 35) for i in range(n)]
    kcoefs.reverse()
    #kcoefs.sort()
    kexpr =  [varnames, kcoefs]
    #print kexpr
    
    prob.linear_constraints.add(lin_expr = [kexpr],
                                senses = ["L"],
                                rhs = [b],
                                names = kpnames)

    return prob


def gen_min_covers(prob):
    row = prob.linear_constraints.get_rows(0)
    rhs   = prob.linear_constraints.get_rhs()
    A = row.val
    b = rhs[0]
    
    min_covers = []
    IP = powerset(A)

    for c in IP:
        if test_cover_minimal(c[1], b):
            min_covers.append(c[0])

    for cover in min_covers:
        ext_cover = extend_cover(cover, A)
        #print cover
        #print ext_cover

        ext_coefs = [1] * len( ext_cover ) #extend the cover here
        prob.linear_constraints.add( lin_expr = [[ext_cover, ext_coefs]] ,
                                     senses = ["L"],
                                     rhs = [ len(ext_cover) - 1 ] )
        """
        # generate regular minimal cover here
        coefs = [1] * len( cover )
        prob.linear_constraints.add( lin_expr = [[cover, coefs]] ,
                                     senses = ["L"],
                                     rhs = [ len(cover) - 1 ] )
        """
    return min_covers

#def gen_ext_covers(prob):

def gen_lift_covers(prob):
    row = prob.linear_constraints.get_rows(0)
    rhs   = prob.linear_constraints.get_rhs()
    A = row.val
    b = rhs[0]

    min_covers = []
    IP = powerset(A)
    
    for c in IP:
        if test_cover_minimal(c[1], b):
            min_covers.append(c[0])

    #print min_covers

    for cover in min_covers:
        A_coefs_cov = [A[i] for i in cover]

        remainder = list(set(range(len(A))) - set(cover))

        remainder.sort()
        A_coefs_rem = [A[i] for i in remainder]

        rem_coefs = [0] * len( remainder )
        cov_coefs = [1] * len( cover )

        mu = cumsum(A_coefs_cov)
        mu = [0] + mu
        lamda = mu[-1] - b
        #print mu
        for i in range( len(remainder) ):
            a = A[ rem_coefs[i] ]
            for h in range(len(cover)):
                if  mu[h] <= a and a <= mu[h+1] - lamda:
                    rem_coefs[i] = h
                elif mu[h+1] - lamda + 1 <= a and a <= mu[h+1] - 1:
                    rem_coefs[i] = h+1
                    
        temp_ind = cover + remainder
        temp_val = cov_coefs + rem_coefs

#        print temp_ind
        print temp_val

        prob.linear_constraints.add( lin_expr = [[temp_ind, temp_val]] ,
                                     senses = ["L"],
                                     rhs = [ len(cover) - 1 ])

    return 0

"""
min_covers = []
A = [random.randint(1, 20) for i in range(10)]
A.sort()
IP = powerset(A)  #the powerset and its indices
b = 20

for c in IP:
    if test_cover_minimal(c[1], b):
        min_covers.append(c)
"""
prob = genkp(6, 5, 30)

prob.write("kp_org.lp")

gen_lift_covers(prob)
#prob.write("kp_with_extended_covers.lp")

prob.write("kp_with_lifted_covers.lp")

#prob = genkp(30, 5, 6)

#prob.write("kp.lp")



